Definition

Define language LL' as NP-hard if LpLL \leq_p L' for every LL \in NP. (polynomial-time reduction from LL to LL')

(see NP, also note that p\leq_p means polynomial-time reduction)


References

  1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 42.